package com.ai.zuochengyun.phase01.class01;

import java.util.PriorityQueue;

/**
 * 上浮过程叫heapInsert
 * 下沉过程叫heapify
 */
public class Code12_Heap {

    public static void main(String[] args) {
        PriorityQueue<Integer> smallRootHeap = new PriorityQueue<>();
        smallRootHeap.add(5);
        smallRootHeap.add(3);
        System.out.println(smallRootHeap.peek());

        PriorityQueue<Integer> bigRootHeap = new PriorityQueue<>((a, b)->{return b-a;});
        bigRootHeap.add(5);
        bigRootHeap.add(3);
        System.out.println(bigRootHeap.peek());
    }

    /**
     * 往上看，和父节点的值比较
     *
     * @param arr
     * @param index
     */
    private static void heapInsert(int[] arr, int index) {
        // 如果当前位置的值比父节点位置的值大，那么值进行交换，形成大根堆
        // 当index来到0位置时，父节点是本身，不满足大于的条件，所以会结束循环
        // 当index在中间位置时，如果值不比父节点的值大，也会结束循环
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            // 当前位置来到父节点的位置
            index = (index - 1) / 2;
        }
    }

    /**
     * 当用户不在给值时，要取最大值，然后要将该值从大根堆中移除
     * 停止的条件：1、较大的孩子都不再比index位置的数大；2、已经没有孩子了
     */
    private static void heapify(int[] arr, int index, int heapSize) {
        // 左孩子下标
        int left = index * 2 + 1;
        // 有左孩子的情况下，才下沉
        while (index < heapSize) {
            // 找到较大孩子对应的下标
            // 存在两种情况：1、有左孩子没有右孩子；2、有左孩子和右孩子
            int largest = left + 1 < heapSize ? (arr[left] > arr[left + 1] ? left : left + 1) : left;
            // 然后和当前节点的值进行比较，如果不大于当前节点，就结束下沉
            if (arr[index] >= arr[largest]) {
                break;
            }
            swap(arr, index, largest);
            // 当前节点来到较大孩子的位置
            index = largest;
            // 继续下一轮，再去看当前节点是否还有子节点
            left = index * 2 + 1;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
